package clasificacion;

/**
 * 
 * @author [La Revancha]
 * 
 */

public class TClasificacion {
	public static final int METODO_CLASIFICACION_SELECCION = 1;
	public static final int METODO_CLASIFICACION_HEAPSORT = 2;
	public static final int METODO_CLASIFICACION_INSERCION = 3;
	public static final int METODO_CLASIFICACION_QUICK = 4;
	
	private int cantidadLlamadas = 0;
	public int getCantidadLlamadas() {
		return cantidadLlamadas;
	}
	private int profundidad = 0;
	public int getProfundidad() {
		return profundidad;
	}
	
	





	
	

	/**
	 * Metodo que ordena un vector utilizando el metodo de clasificacion por
	 * seleccion directa.
	 * 
	 * @param datosParaClasificar
	 * @return el arreglo pasado por parametro ordenado de menor a mayor
	 */

	private int[] seleccion(int[] datosParaClasificar) {

		if (datosParaClasificar == null)
			return null;

		int indiceMenor; // Indice del Menor elemento en el vector
		int claveMenor; // Valor del menor elemento del vector

		for (int i = 0; i < datosParaClasificar.length; i++) {
			indiceMenor = i;
			claveMenor = datosParaClasificar[i];
			for (int j = i + 1; j < datosParaClasificar.length; j++) {
				if (datosParaClasificar[j] < claveMenor) {
					indiceMenor = j;
					claveMenor = datosParaClasificar[j];
				}

			}
			intercambio(datosParaClasificar, i, indiceMenor);

		}

		return datosParaClasificar;
	}
	
	
	/**
	 * Metodo que ordena un vector de mayor a menor por el metodo heapsort
	 * @param datosParaClasificar
	 * @return
	 */

	private int[] ordenarPorHeaspSort(int[] datosParaClasificar) {
		
		
		if (datosParaClasificar == null)
			return null;

		for (int i = (datosParaClasificar.length - 1) / 2; i >= 0; i--) {
			desplazarElemento(datosParaClasificar, i, datosParaClasificar.length - 1);
			
		}
		for (int i = datosParaClasificar.length - 1; i >= 1; i--) {
			
			intercambio(datosParaClasificar, 0, i);
			desplazarElemento(datosParaClasificar, 0, i - 1);
			
		}
		return datosParaClasificar;
	}

	
	/**
	 * Metodo que desplaza los elementos primero y ultimo en el APO
	 * @param datosParaClasificar
	 * @param primero
	 * @param ultimo
	 */
	private void desplazarElemento(int[] datosParaClasificar, int primero, int ultimo) {
		
		if (primero < ultimo) {
			
			int actual = primero;
			
			while (actual <= ultimo / 2) {
				if (ultimo == 2 * actual) { 
					if (datosParaClasificar[actual] < datosParaClasificar[actual * 2]) {
						intercambio(datosParaClasificar, actual, 2 * actual);
						actual = 2 * actual;
					} else
						actual = ultimo;
				} else { 
					int mayor = 0;
					if (datosParaClasificar[2 * actual] > datosParaClasificar[2 * actual + 1]) {
						mayor = 2 * actual;
					} else
						mayor = 2 * actual + 1;
					if (datosParaClasificar[actual] < datosParaClasificar[mayor]) {
						intercambio(datosParaClasificar, actual, mayor);
						actual = mayor;
					} else
						actual = ultimo;
				}
			}
		}
	}

	/***
	 * Metodo que clasifica el areglo datosParaClasificar por insercion directa
	 * @param datosParaClasificar, areglo con los datos a ordenar
	 * @return el arreglo ordenado
	 */
	public int[] IncercionDirecta(int[] datosParaClasificar) {
		
		int aux = 0;
		
		int j = 0;
		
		for (int i = 1; i < datosParaClasificar.length; i++) {
			
			aux = datosParaClasificar[i];
			j = i - 1;
			
			while (j >= 0 && aux < datosParaClasificar[j]) {
				
				datosParaClasificar[j + 1] = datosParaClasificar[j];
				j--;
				
			}
			
			datosParaClasificar[j + 1] = aux;
		}

		return datosParaClasificar;
		
	}
	
	/**
	 * Metodo que ejecuta el ordenamiento del vector por quiksort
	 * @param datosParaClasificar
	 */
	private int[] ordenarPorQuickSort(int[] datosParaClasificar){
		//Chequo, armo las estructuras y le paso a PorQuickSort
		if(datosParaClasificar != null){
			int contador = 0;
			int [] out = porQuickSort(datosParaClasificar, 0, datosParaClasificar.length-1, contador);
			System.out.println("NIVEL = "+contador);
			return out;
		}else{
			return null;
		}
	}
	
	public int[] porQuickSort(int[] datosParaClasificar, int i, int j, int contador) {
		if(datosParaClasificar.length>1)
			cantidadLlamadas++;
		
		
		int izq = i;
        int der = j;
        int nivelIzq =0;
        int nivelDer =0;
        System.out.println("NIVEL ="+contador);
        int posicionPivote = encuentraPivote(izq, der, datosParaClasificar);
        if (posicionPivote >= 0) {
            int pivote = datosParaClasificar[posicionPivote];
            while (izq <= der) {
                while ((datosParaClasificar[izq] < pivote) && (izq < j)) {
                    izq++;
                }
                while ((pivote < datosParaClasificar[der]) && der > i) {
                    der--;
                }
                if (izq <= der) {
                    intercambio(datosParaClasificar, izq, der);
                    izq++;
                    der--;
                }
            }
            
            	if (i < der) {
            		nivelIzq++;
            		porQuickSort(datosParaClasificar, i, der,contador++);
            		
            	}
            	if (izq < j) {
            		nivelDer++;
            		porQuickSort(datosParaClasificar, izq, j, contador++);
            		
            	}
            if(nivelIzq<nivelDer)
            	contador += nivelIzq;
            else
            	contador += nivelDer;
            
        }
        return datosParaClasificar;
	}
	
	private int[] porInsercionAcotado(int[] datosParaClasificar,int i, int j) {
		if(datosParaClasificar != null){
			int j1 = j;
			for(int i1 = i+1 ; i1 < j1; i1++){
				int p = i1-1;
				while ((p >= i) && (datosParaClasificar[p] > datosParaClasificar[p+1])){
					intercambio(datosParaClasificar, p , p+1);
					p--;
				}
			}
			return datosParaClasificar;
		}
		return null;
	}
	 
	private int encuentraPivote(int izq, int der, int[] datosParaClasificar) {
		int i =1;
		if(datosParaClasificar.length>1){
			while(datosParaClasificar[izq]==datosParaClasificar[i]){
				i++;
			}
			if(datosParaClasificar[izq]>datosParaClasificar[i])
				return izq;
			else
				return der;
		}
		else return 0;
	}
	
	/**
	 * Metodo que intercambia la posicion primero y la posicion ultimo en el
	 * vector que se pasa por parametro
	 * 
	 * @param datosParaClasificar
	 * @param primero
	 *            , indice de un elemento del vector que va a ser intercambiado
	 * @param ultimo
	 *            , indice de un elemento del vector que va a ser intercambiado
	 */
	private void intercambio(int[] datosParaClasificar, int primero, int ultimo) {

		int aux = datosParaClasificar[primero];
		datosParaClasificar[primero] = datosParaClasificar[ultimo];
		datosParaClasificar[ultimo] = aux;

	}

	
	
	/**
	 * Metodo que se encarga de llamar al algoritmo de ordenacion con el que se
	 * quiere ordenar el vector
	 * 
	 * @param datosParaClasificar
	 * @param metodoClasificacion
	 * @return el vector ordenado de menor a mayor por el metodo seleccionado
	 */

	public int[] clasificar(int[] datosParaClasificar, int metodoClasificacion) {
		switch (metodoClasificacion) {
		case METODO_CLASIFICACION_SELECCION:
			return seleccion(datosParaClasificar);
		case METODO_CLASIFICACION_HEAPSORT:
			return ordenarPorHeaspSort(datosParaClasificar);
		case METODO_CLASIFICACION_INSERCION:
			return IncercionDirecta(datosParaClasificar);
		case METODO_CLASIFICACION_QUICK:
			return ordenarPorQuickSort(datosParaClasificar);
		default:
			System.err.println("Este codigo no deberia haberse ejecutado");
			return null;
		}
	}
}
